<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">

	<title>Question 1: Is Bigger Smarter?</title>
</head><body>
<h1>Question 1: Is Bigger Smarter?</h1>

<h2>The Problem</h2>
<p>

Some people think that the bigger an elephant is, the smarter it is.
To disprove this, you want to take the data on a collection of elephants
and put as large a subset of this data as possible into a sequence
so that the weights are increasing, but the IQ's are decreasing.

</p><p>

The input will consist of data for a bunch of elephants, one elephant per
line, terminated by the end-of-file.
The data for a particular elephant will consist of a pair of integers:
the first representing its size in kilograms and the second representing its
IQ in hundredths of IQ points.
Both integers are between 1 and 10000.
The data will contain information for at most 1000 elephants.
Two elephants may have the same weight, the same IQ, or even the same weight
and IQ.

</p><p>

Say that the numbers on the i-th data line are <tt>W[i]</tt> and <tt>S[i]</tt>.
Your program should output a sequence of lines of data; the first line should
contain a number <tt>n</tt>; the remaining <tt>n</tt> lines should
each contain a single positive integer (each one representing an elephant).
If these <tt>n</tt> integers are <tt>a[1]</tt>, <tt>a[2]</tt>,..., <tt>a[n]</tt>
then it must be the case that
</p><pre>   W[a[1]] &lt; W[a[2]] &lt; ... &lt; W[a[n]]
</pre>
and
<pre>   S[a[1]] &gt; S[a[2]] &gt; ... &gt; S[a[n]]
</pre>
In order for the answer to be correct, <tt>n</tt> should be as large as
possible.
All inequalities are strict: weights must be strictly increasing, and IQs
must be strictly decreasing.
There may be many correct outputs for a given input, your program only
needs to find one.

<p></p>

<h2>Sample Input</h2>

<pre>6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
</pre>

<h2>Sample Output</h2>

<pre>4
4
5
9
7
</pre>
</body></html>